﻿//最少的完全平方数
//https://www.nowcoder.com/practice/4b2f5d4c00f44a92845bdad633965c04?tpId=230&tqId=40431&ru=/exam/oj
//#include <iostream>
//#include <cstring>
//
//using namespace std;
//
//const int N = 1e4 + 10;
//int n;
//int dp[N];
//
//int main()
//{
//	cin >> n;
//	memset(dp, 0x3f, sizeof dp);
//	dp[0] = 0;
//
//	for (int i = 1; i * i <= n; i++)
//	{
//		for (int j = i * i; j <= n; j++)
//		{
//			dp[j] = min(dp[j], dp[j - i * i] + 1);
//		}
//	}
//
//	cout << dp[n] << endl;
//
//	return 0;
//}


//字符编码
// https://www.nowcoder.com/practice/c471efdbd33a4a979539a91170c9f1cb?tpId=128&tqId=33774&ru=/exam/oj
//#include <iostream>
//#include <algorithm>
//#include <queue>
//#include <string>
//
//using namespace std;
//
//string s;
//
//void func()
//{
//	int n = s.size();
//	sort(s.begin(), s.end());
//
//	priority_queue<int, vector<int>, greater<int>> pq;
//	int left = 0, right = 0;
//	while (right < n)
//	{
//		if (s[left] == s[right])
//			right++;
//		else if (s[left] != s[right])
//		{
//			pq.push(right - left);
//			left = right;
//		}
//	}
//	pq.push(right - left);
//
//	int count = 0;
//	while (pq.size() > 1)
//	{
//		int a = pq.top(); pq.pop();
//		int b = pq.top(); pq.pop();
//		pq.push(a + b);
//		count += a + b;
//	}
//
//	cout << count << endl;
//}
//
//int main()
//{
//
//	while (cin >> s)
//	{
//		func();
//	}
//
//	return 0;
//}


//神奇的字母（二）
// https://ac.nowcoder.com/acm/problem/205832
//using namespace std;
//
//#include <iostream>
//
//int hash1[26];
//
//int main()
//{
//	char ch;
//	while (cin >> ch)
//	{
//		if (ch >= 'a' && ch <= 'z')
//			hash1[ch - 'a']++;
//	}
//	
//	int ret = 0;
//	int _char = 0;
//	int i = 0;
//	for (; i < 26; i++)
//	{
//		if (hash1[i] > ret)
//		{
//			ret = hash1[i];
//			_char = i;
//		}	
//	}
//	
//	cout << char('a' + _char) << endl;
//
//
//	return 0;
//}


//#include <iostream>
//#include <cstring>
//
//using namespace std;
//
//const int N = 1e4 + 10;
//
//int n;
//int dp[N];
//
//int main()
//{
//	cin >> n;
//
//	memset(dp, 0x4f, sizeof(dp));
//	// memset(dp, 0x3f, sizeof dp);
//	dp[0] = 0;
//
//	for (int i = 1; i * i <= n; i++)
//	{
//		for (int j = i * i; j <= n; j++)
//		{
//			//容积为就j时，物品的最少个数
//			dp[j] = min(dp[j], dp[j - i * i] + 1);
//		}
//	}
//
//	cout << dp[n] << endl;
//
//	return 0;
//}


//多态场景的⼀个选择题
//#include <iostream>
//
//using namespace std;
//
//class A
//{
//public:
//	virtual void func(int val = 1) { std::cout << "A->" << val << std::endl; }
//	virtual void test() { func(); }
//};
//
//class B : public A
//{
//public:
//	void func(int val = 0) { std::cout << "B->" << val << std::endl; }
//};
//
//int main(int argc, char* argv[])
//{
//	B* p = new B;
//	//p->test();
//
//	//p->func();
//
//	//A的对象
//	A* a = p;
//	//满足多态，调用B中的func(),但是指针为A的指针，绑定的默认参数为Afunc()中的1
//	//C++ 中，虚函数的默认参数值是在编译时根据调用函数的指针 / 引用类型确定的，而非运行时根据对象实际类型确定。
//	a->func();         // 输出 B->1（静态绑定默认参数）
//	//p->func();         // 输出 B->1（静态绑定默认参数）
//
//	//p->func(2);        // 输出 B->2（显式传参覆盖默认值）
//	//a->func(3);        // 输出 B->3（同上）
//
//	return 0;
//}